//给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。 
//
// 
//
// 示例 1： 
//
// 输入：
//    3
//   / \
//  9  20
//    /  \
//   15   7
//输出：[3, 14.5, 11]
//解释：
//第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
// 
//
// 
//
// 提示： 
//
// 
// 节点值的范围在32位有符号整数范围内。 
// 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 
// 👍 294 👎 0

package com.cute.leetcode.editor.cn;

import java.util.*;

public class AverageOfLevelsInBinaryTree {
    public static void main(String[] args) {
        TreeNode root = new  TreeNode(3);
        TreeNode node1 = new TreeNode(4);
        TreeNode node2 = new TreeNode(5);
        TreeNode node3 = new TreeNode(1);
        TreeNode node4 = new TreeNode(3);
        TreeNode node5 = new TreeNode(1);
        root.left = node1;root.right = node2;node1.left = node3;node1.right =node4;node2.right = node5;
        new AverageOfLevelsInBinaryTree().new Solution().averageOfLevels(root);
    }
    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /*List<Double> res = new ArrayList<>();
    Map<Integer,Double> sumMap = new HashMap<>();
    Map<Integer,Integer> countMap = new HashMap<>();
    public List<Double> averageOfLevels(TreeNode root) {
        bfs(root, 0);
        for (int i = 0; i < sumMap.size() ; i++) {
            res.add(i, (double) (sumMap.get(i)/countMap.get(i)));
        }
        return res;
    }
    public void bfs(TreeNode root, int index){
        if (root == null) return;
        if (!sumMap.containsKey(index)){
            sumMap.put(index, (double) root.val);
            countMap.put(index, 1);
        }else {
            sumMap.put(index, sumMap.get(index)+root.val);
            countMap.put(index, countMap.get(index)+1);
        }
        bfs(root.left, index+1);
        bfs(root.right, index+1);

    }*/

    /**
     * 题解中使用的queue来实现的广度优先遍历
     * 因为队列是先进先出，所以在遍历当前层节点的时候，只要一开始确定了count之后，遍历的时候即使再添加，也会算到下一层中去
     * 这个方法是真的妙
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//这里先添加第一层的root节点
        while (!queue.isEmpty()){
            double sum = 0;//当前层求和的结果
            int count = queue.size();//当前层节点的个数
            for (int i = count; i >=1 ; i--) {//遍历当前层所有节点
                TreeNode node = queue.poll();//取出当前层的节点
                sum += node.val;//进行求和
                //TODO 这里是很好的方法，将下一层的节点添加到了队列，但是本次循环是访问不到的
                if (node.left!=null) queue.offer(node.left);
                if (node.right!=null) queue.offer(node.right);
            }
            ans.add(sum / count);//计算本层的均值并添加，进入下一层的循环
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}